The present invention is directed generally to the field of autonomous or computer-aided navigation, and more particularly to systems and methods for classifying sensor data and inferring ground height for use in generating terrain models that may be used for autonomous or computer-aided navigation.
Outdoor environments such as those encountered in agriculture, mining, and the exploration of hazardous environments often have no structured features, such as road markers, straight walls, a flat ground plane, etc. For that reason, outdoor environments are viewed as being unstructured. The unstructured nature of those environments has often been cited as one of the reasons that navigating within those environments is considered to be so challenging.
Early work in terrain perception was applied to environments with smooth terrain and discrete obstacles and achieved good results in those domains by looking at the height above the ground surface of the sensor readings from individual grid cells. However, as shown in FIG. 1, the presence of vegetation makes the problem much more difficult because forward looking sensors such as a laser range-finder or stereo cameras produce range points above the ground surface but these range points do not represent obstacles. Classification of vegetation (also common in the remote sensing community) could allow an autonomous system to drive through vegetated areas, but classification is not sufficient for this task either because a grassy area on a steep slope may be dangerous to drive on whereas the same grass on a flat area could be easily traversable. A terrain model needs both classification and the ground height to allow safe navigation.
A number of researchers have investigated methods that use range data to discriminate sparse vegetation (as shown in FIG. 1) from solid substances such as the ground or obstacles. These techniques exploit the fact that range measurements often penetrate sparse vegetation, but do not penetrate solid obstacles. The properties used for discrimination fall into two categories: shape and density.
Shape-based methods begin with a 3D cloud of range points and look at local features of the data points to discriminate between the random spread of points in sparse vegetation and the organized structure of points on solid objects. Researchers have modeled the statistics of laser penetration in grass to find solid objects, and they have compared measurements across time and space to filter out areas where the penetration is continually changing. A comparison between techniques that look for the range shadow of solid obstacles and techniques based on local point statistics is given in M. Herbert et al., “Evaluation and comparison of terrain classification techniques from LADAR data for autonomous navigation,” in 23rd Army Science Conference, December 2002. The strategy of computing local statistics about the spread of points was expanded in N. Vandapel et al., “Natural terrain classification using 3-D ladar data.” In IEEE Int. Conf on Robotics and Automation, April 2004. to discriminate between sparse vegetation, solid surfaces, linear structures such as branches, and even concertina wire N. Vandapel et al., “Finding organized structures in 3-d ladar data”, in IEEE Int. Conf on Intelligent Robots and Systems, 2004.
Density-based methods attempt to use range measurements to explicitly measure the density of objects in the environment. This has been done by dividing the world into small volumes of space and then maintaining density scores by keeping track of ladar hits and pass-through or ladar and radar measurements.
The above methods have shown promising results in sparse vegetation, but they do not address the problem of estimating the ground surface in dense vegetation where the ground is completely hidden as in FIG. 2. We have used online learning methods to automatically learn the ground height in vegetation from features (C. Wellington et al., “Online adaptive rough-terrain navigation in vegetation,” in IEEE Int. Conf on robotics and Automation, April, 2004), but the resulting ground surface estimates were very noisy. One reason for this is that this method makes the strong assumption of independence between terrain patches and makes predictions locally without incorporating spatial context. That can make it difficult to disambiguate data from tall vegetation and data from short vegetation, resulting in poor estimates of the hidden ground height. Without an accurate ground height estimate, an autonomous system may not be able to detect hazards such as steep slopes or ditches, and it may not be able to properly disambiguate solid obstacles from the ground surface. Thus, a need exists for a system and method for deriving an accurate terrain model which can be used to autonomously pilot a vehicle.